package _03_recursion.problems;

import org.junit.Test;

/**
 * @author: mornd
 * @dateTime: 2023/6/1 - 15:27
 * 青蛙跳台阶问题，求n个台阶，青蛙有多少种跳法，图示
 *      青蛙每次可以跳1阶或者多阶（多阶没上限）
 *      只能向上跳
 *      1，2台阶特殊处理   跳法 = f(n-1) + f(n-2)
 */
public class Flog {
    @Test
    public void test() {
        for (int i = 1; i <= 10; i++) {
            System.out.println("台阶数：" + i + "\t多少种跳法：" + foo(i));
        }
    }

    /**
     *
     * @param n 台阶数
     * @return 有多少种跳法
     */
    int foo(int n) {
        if(n == 1 || n == 2) {
            // 1 阶只有1种跳法 [1]
            // 两阶有两种 [1,1] [2]
            return n;
        }
        return foo(n - 1) + foo(n - 2);
    }
}
